#ifndef __LINKLIST_H_
#define __LINKLIST_H_

#include<cstddef>
#include<iostream>
#include"DynamicArray.h"

using ElementType = int;

class LinkList
{
public:
    LinkList();
    LinkList(const LinkList& list);
    LinkList& operator=(const LinkList& list);
    ~LinkList();

    //插入
    //尾插法
    void InsertFail(const ElementType& element);
    //头插法
    void InsertHead(const ElementType& element);
    //中间插入
    void InsertByIndex(size_t index, const ElementType & element);

    //删除
    //按位删除
    void RemoveByIndex(size_t index);
    //按值删除
    void RemoveByElement(const ElementType & element);

    //按位查找
    ElementType* FindByIndex(size_t index);
    //按值查找
    DARRAY::DynamicArray FindByElement(const ElementType & element);

    void show();

    //按位置修改
    void UpdataByIndex(size_t index, const ElementType& element);
    //按值修改
    void UpdataByElement(const ElementType& oldValue,const ElementType& newValue);

    //排序
    //冒泡排序
    void BubbleSort();

    //快速排序
    void Sort();

    //倒数第n个元素
    ElementType* GetReserveIndex(size_t index);

    //归并
    LinkList Merge(const LinkList & list);

    //交并补
    LinkList FdIntrSctn(const LinkList& list);
    LinkList FdUnionSet(const LinkList & list);
    LinkList FindDifference(const LinkList & list); 


    //链表的逆序
    void Reserve();
    //递归逆序
    void Reserve2();

private:
    struct Node
    {
        Node(const ElementType& value)
        {
            this->value = value;
            next = nullptr;
        }
        ElementType value;//数据域
        Node *next;//指针域
    };
    void FastSort(Node *start, Node *end);
    Node *reserve(Node *node);
    Node *head; //头指针
    size_t size;//元素的个数
};

#endif